Wavelength Division Multiplexing (WDM) networks are considered to be the most promising candidate for next generation backbone networks and WDM ring networks are being widely deployed by a growing number of telecom carriers to support Synchronous Optical Network (SONET)/Synchronous Digital Hierarchy (SDH) self-healing rings. WDM technologies allow carriers to build networks that scale in capacity to meet the unprecedented rate of growth of Internet traffic. These technologies provide fundamental data network architectures that are simple, low-cost and easy to manage.
As shown in FIG. 1A, the physical topology of a WDM ring network 100 consists of a plurality of optical nodes 102 and a plurality of bi-directional fiber links 104 there between. In this example, only one link 104 is shown between each node 102, but it should be apparent that there may be more than one and that the number of links between nodes need not be the same. Further, each link 104 is capable of transporting a limited number of wavelength channels. A node is considered to be capable of routing any incoming wavelength channel on any of the incoming links 104 to any wavelength channel on any of the outgoing fibers. In addition to such routing and switching functions, each node 102 may consist of several SONET/SDH add/drop multiplexers (ADMs).
As shown in FIG. 1B, between pairs of nodes 102 in the network and using links 104, light-paths 106 can be set up. As used herein, a light-path, also called optical path, represents a direct optical connection between a pair of nodes (not necessarily adjacent in the ring) without any intermediate electronics, including ADMs at any intermediate node. As shown in FIG. 1B, certain links 104 can carry more than one wavelength channel or light-path 106. Each wavelength channel or light-path represents traffic at a given optical wavelength traversing both the upstream and downstream directions. The way in which the wavelengths are assigned to a given set of light-paths is one of the most fundamental network design problems for WDM networks.
Recently, significant research has been performed to minimize the number of wavelengths needed for a given set of light-paths, or to minimize the number of blocked light-paths given a fixed number of wavelengths. However, from an engineering and economic perspective, unless the limit on the number of wavelengths is exceeded, the highest-priority optimization objective should be to minimize the overall network cost, rather than minimizing wavelengths and blocked light-paths. And overall network costs are mainly determined by the number of total required SONET add/drop multiplexers (ADMs), instead of the number of wavelengths, employed in the network. Further, according to dense WDM (DWDM) applications, as well as the recently completed ITU-T Recommendation G.692, the technology allows up to around 40 different wavelengths per fiber in the 1550 nm window with 100 GHz (about 0.8 nm) spacing in the flat operating gain band (1530–1560 nm) of the present Erbium-Doped Fiber Amplifiers (EDFA).
It has been reported that the minimum ADM problem is NP-complete, which means that there is no optimal solution for finding the minimum required ADMs for a given set of light-paths with a polynomial computational complexity. Rather, several heuristics have been proposed to minimize the number of ADMs in WDM ring networks. These proposals can broadly be categorized as either (1) solutions with light-paths splitting or (2) solutions without light-paths splitting.
As for the first category of proposals, an approach called Cut-First has been advanced. See O. Gerstel et al., “Wavelength Assignment in a WDM Ring to Minimize Cost of Embedded SONET Rings,” Proc. of IEEE INFOCOM '98, March 1998, for details. However, proposals such as the Cut-First approach, that are based on light-paths splitting, are not desired because it requires that light-paths be split into several segments and that data be transferred electrically between the segments. Although this is a valid option for SONET rings, it involves higher port and cross-connect costs than approaches that do not require light-paths splitting due to the need for additional electro-optics conversions.
As for the category of proposals that do not require splitting of light-paths, a heuristic called Assign First was presented by O. Gerstel et al. The basic idea is that it initially assigns all light-paths that pass through a carefully selected node with unique wavelengths, and then greedily assign wavelengths to the remaining light-paths node by node. Further, in L. Liu et al., “Wavelength Assignment in WDM Rings to Minimize SONET ADMs,” Proc. of IEEE INFOCOM '2000, March 2000, three greedy segmenting approaches were proposed, called Iterative Merging, Iterative Matching and Euler Cycle Decomposition. In the Iterative Merging approach, each light-path is initiated as an individual segment. At each iteration, three possible operations are performed in decreasing priority: (1) merge two noncircular segments into a circle segment, (2) split a noncircular segment into two noncircular segments and merge one of them with another noncircular segment into a circle segment, and (3) merge two noncircular segments into a larger noncircular segment. In the Iterative Matching approach, the segments are merged according to the maximum matching at a node based on a constructed bipartite graph, which indicates the set of segments ending at a node and the set of segments starting at a node. The Euler Cycle Decomposition method aims to find the best starting point by enumerating all possible starting points for an Eulerian circuit over the constructed uniform set of light-paths, aiming at the minimum number of noncircular segments for the decomposition of the Eulerian circuit.
It has been reported by L. Liu et al. through a set of randomized simulation studies that among all of the above heuristics, Iterative Merging demonstrates the best performance in general regarding the number of shared ADMs.
However, all the above conventional approaches are flawed in various respects. For example, all of the conventional approaches rely on static lookup methods which is a less than efficient way to solve the minimum ADM problem in WDM ring networks.